// 深度优先搜索  Depth-First Search，DFS
// 栈 
// 通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问

// 广度优先搜索  Breadth-First Search，BFS
// 队列 
// 通过将顶点存入队列中，最先入队列的顶点先被探索

// 当要标注已经访问过的顶点时，我们用三种颜色来反映它们的状态。
//  白色：表示该顶点还没有被访问。
//  灰色：表示该顶点被访问过，但并未被探索过。
//  黑色：表示该顶点被访问过且被完全探索过。
// 这就是访问每个顶点最多两次的原因

const Queue = require('../Utils/queue.js');
const Stack = require('../Utils/stack.js');
class Graph {
  constructor() {
    // 存储所有顶点
    this.vertices = [];
    // 存储所有邻接表
    this.adjList = new Map();
  }

  // 添加顶点
  addVertex(v) {
    this.vertices.push(v);
    this.adjList.set(v, []);
  }

  addEdge(v, w) {
    this.adjList.get(v).push(w);
    this.adjList.get(w).push(v);
  }

  toString() {
    let s = '';
    for (let i = 0; i < this.vertices.length; i++) {
      s += this.vertices[i] + ' -> ';
      let neighbors = this.adjList.get(this.vertices[i]);
      for (let j = 0; j<neighbors.length; j++) {
        s += neighbors[j] + ' ';
      }
      s += '\n';
    }
    return s;
  }

  // 初始化所有顶点的状态 为white
  initializeColor() {
    let color = [];
    for (let i = 0; i < this.vertices.length; i++) {
      color[this.vertices[i]] = 'white';
    }
    return color;
  }

  /**
   * 广度优先搜索
   * 通过将顶点存入队列，最先入队列的顶点先被探索
   * @param {*} v 顶点
   * @param {*} callback 回调函数
   * @memberof Graph
   */
  BFS(v, callback) {
    // 初始化顶点状态
    const color = this.initializeColor();
    // 创建队列
    const queue = new Queue();
    // 把顶点加入队列
    queue.enqueue(v);
    while(!queue.isEmpty()) {
      // 取出一个点
      const u = queue.dequeue();
      // 取出和该点相邻的所有点
      const neighbors = this.adjList.get(u);
      // 把该点设为grey, 表示已经访问，还没探索
      color[u] = 'grey';
      // 开始探索
      for (let i = 0; i < neighbors.length; i++) {
        let w = neighbors[i];
        // 如果相邻的点是white, 表示没有访问到
        if(color[w] === 'white') {
          // 设置为grey  访问到了
          color[w] = 'grey';
          // 加入队列，等待探索
          queue.enqueue(w);
        }
      }
      // 探索完成，设置为black;
      color[u] = 'black';
      // 如果有回调，则执行回调函数
      if (callback) {
        callback(u);
      }
    }
  }
}

const graph = new Graph();
const myVertices = ['A','B','C','D','E','F','G','H','I'];
for (let i = 0; i< myVertices.length; i++){
  graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

console.log(graph.toString());
